Vertex Cover
정점 집합 S가 있을 때, 모든 간선은 양 끝점 중 하나가 S 에 포함되어야 한다.
최소 정점 커버란?
정점 집합 S가 있을 때, 모든 간선은 양 끝점 중 적어도 하나가 S 에 포함되어야 한다. 여러 Vertex Cover 중에 크기가 가장 작은 Vertex Cover 를 의미한다.
근사
degree 가 높은 점을 우선 선택
근사 비율은 이다.
선분을 선택
선택된 선분의 양 끝점에 인접한 선분이 모두 커버된다. 정점 커버는 선택된 각 선분의